package com.test.daily.leetcode.y2022.m06.day0610.v01;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/10 上午 09:26
 * @version: 1.0
 */
public class Solution {
    public static int right(int[] arr, int n, int a, int b) {
        int[] times = new int[arr.length];
        int[] drink = new int[n];
        return forceMake(arr, times, 0, drink, n, a, b);
    }

    public static int forceMake(int[] arr, int[] times, int kth, int[] drink, int n, int a, int b) {
        if(kth == drink.length){
            int[] sortedDrink = drink;
            Arrays.sort(sortedDrink);
            return forceWash(sortedDrink, a, b, 0, 0, 0);
        } else {
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < drink.length; i++){
                int work = arr[i];
                int pre = times[i];
                drink[kth] = pre + work;
                times[i] = pre + work;
                min = Math.min(min, forceMake(arr, times, kth + 1, drink, n, a, b));
                drink[kth] = 0;
                times[i] = pre;
            }
            return min;
        }
    }
    /**
     * 
     * @param drinks 喝完咖啡的时间点
     * @param a 洗咖啡杯的时间
     * @param b 挥发干净的时间
     * @param index 来到了index号人的咖啡杯,或者洗，或者挥发
     * @param washLine 咖啡机的时间线
     * @param time 最大的时间线
     * @return
     */
    public static int forceWash(int[] drinks, int a, int b, int index, int washLine, int time) {
        if(drinks.length == index){
            return time;
        }
        // 来到了index号人
        // 选择一: 选择洗杯子
        int wash = Math.max(drinks[index], washLine) + a;
        int ans1 = forceWash(drinks, a, b, index + 1, wash, Math.max(wash, time));

        // 选择二: 选择挥发
        int dry = drinks[index] + b;
        int ans2 = forceWash(drinks, a, b, index+1, washLine, Math.max(dry, time));
        return Math.max(ans1, ans2);
    }

    public static class Machine {
        public int timePoint;
        public int workTime;

        public Machine(int t, int w){
            timePoint = t;
            workTime = w;
        }
    }
    public static class MachineComparator implements Comparator<Machine> {
        @Override
        public int compare(Machine o1, Machine o2) {
            return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
        }
    }
    public static int minTime1(int[] arr, int n, int a, int b){
        PriorityQueue<Machine> heap = new PriorityQueue<>();
        for(int i = 0; i < arr.length; i++){
            heap.add(new Machine(0, arr[i]));
        }
        int[] drinks = new int[n];
        for (int i = 0; i < n; i++) {
            Machine cur = heap.poll();
            cur.timePoint += cur.workTime;
            drinks[i] = cur.timePoint;
            heap.add(cur);
        }
        return bestTime(drinks, a, b, 0, 0);
    }
    // drinks 所有杯子可以开始洗的时间
    // wash 单杯洗干净的时间
    // air 挥发的时间
    // free 洗的机器什么时候可以用
    // drinks[index....]都变干净,最早的结束时间
    public static int bestTime(int[] drinks, int wash, int air, int index, int free){
        if(index == drinks.length){
            return 0;
        }
        int selfClean1 = Math.max(drinks[index], free) + wash;
        int restClean1 = bestTime(drinks, wash, air, index+1, selfClean1);
        int p1 = Math.max(selfClean1, restClean1);
        // index号杯子 决定挥发
        int selfClean2 = drinks[index] + air;
        int restClean2 = bestTime(drinks, wash, air, index+1, free);
        int p2 = Math.max(selfClean2, restClean2);
        return Math.min(p1, p2);
    }
    public static int minTime2(int[] arr, int n, int a, int b){
        PriorityQueue<Machine> heap = new PriorityQueue<Machine>(new MachineComparator());
        for (int i = 0; i < arr.length; i++) {
            heap.add(new Machine(0, arr[i]));
        }
        int[] drinks = new int[n];
        for (int i = 0; i < n; i++) {
            Machine cur = heap.poll();
            cur.timePoint += cur.workTime;
            drinks[i] = cur.timePoint;
            heap.add(cur);
        }
        return bestTimeDp(drinks, a, b);
    }
    public static int bestTimeDp(int[] drinks, int wash, int air){
        int N = drinks.length;
        int maxFree = 0;
        for (int i = 0; i < drinks.length; i++) {
            maxFree = Math.max(maxFree, drinks[i]) + wash;
        }
        int[][] dp = new int[N + 1][maxFree + 1];
        for(int index = N - 1; index >= 0; index--){
            for(int free = 0; free <= maxFree; free++){
                int selfClean1 = Math.max(drinks[index], free) + wash;
                if(selfClean1 > maxFree){
                    break; // 因为后面的也不用填了
                }
                // index号杯子 决定洗
                int restClean1 = dp[index+1][selfClean1];
                int p1 = Math.max(selfClean1, restClean1);
                // index号杯子 决定挥发
                int selfClean2 = drinks[index] + air;
                int restClean2 = dp[index+1][free];
                int p2 = Math.max(selfClean2, restClean2);
                dp[index][free] = Math.min(p1, p2);
            }
        }
        return dp[0][0];
    }
}











